//
// 红黑树
// https://www.cnblogs.com/skywang12345/p/3624177.html
// Created by 麻再挺 on 2021/12/20.
//

#ifndef DATA_STRUCTURE_C_RB_SEARCH_H
#define DATA_STRUCTURE_C_RB_SEARCH_H

#include <stdio.h>
#include <stdlib.h>

// 红色节点
#define RED 0
// 黑色节点
#define BLACK 1

// 红黑树类型
typedef int RBType;

// 红黑树节点
typedef struct RBTreeNode {
    // 颜色
    int color;
    // 关键字
    RBType key;
    // 左孩子
    struct RBTreeNode *left;
    // 右孩子
    struct RBTreeNode *right;
    // 父节点
    struct RBTreeNode *parent;
} RBNode, *RBTree;

// 红黑树的根
typedef struct RBRoot {
    RBNode *node;
} RBRoot;

/**
 * 创建红黑树
 * @return 红黑树的根
 */
RBRoot *RB_Create_Tree();

/**
 * 销毁红黑树
 * @param root
 */
void RB_Destroy_Tree(RBRoot *root);

/**
 * 将节点插入到红黑树中
 * @param root 红黑树根
 * @param key 键
 * @return 插入成功返回 0; 失败返回 -1
 */
int RB_Insert_Tree(RBRoot *root, RBType key);

/**
 * 删除节点
 * @param root 红黑树根
 * @param key 键
 */
void RB_Delete_Tree(RBRoot *root, RBType key);

/**
 * 前序遍历"红黑树"
 * @param root 红黑树根
 */
void RB_Pre_Order_Tree(RBRoot *root);

/**
 * 中序遍历"红黑树"
 * @param root 红黑树根
 */
void RB_In_Order_Tree(RBRoot *root);

/**
 * 后序遍历"红黑树"
 * @param root 红黑树根
 */
void RB_Post_Order_Tree(RBRoot *root);

/**
 * (递归实现)查找"红黑树"中键值为key的节点
 * @param root 红黑树根
 * @param key 键
 * @return 找到的话，返回0；否则，返回-1
 */
int RB_Search_Tree(RBRoot *root, RBType key);

/**
 * (非递归实现)查找"红黑树"中键值为key的节点
 * @param root 红黑树根
 * @param key 键
 * @return 找到的话，返回0；否则，返回-1
 */
int RB_Iterative_Search_Tree(RBRoot *root, RBType key);

/**
 * 返回最小结点的值(将值保存到val中)
 * @param root 红黑树根
 * @param val 值
 * @return 找到的话，返回0；否则返回-1
 */
int RB_Minimum_Tree(RBRoot *root, int *val);

/**
 * 返回最大结点的值(将值保存到val中)
 * @param root 红黑树根
 * @param val 值
 * @return 找到的话，返回0；否则返回-1
 */
int RB_Maximum_Tree(RBRoot *root, int *val);

/**
 * 打印红黑树
 * @param root 红黑树根
 */
void RB_Print_Tree(RBRoot *root);

#endif //DATA_STRUCTURE_C_RB_SEARCH_H























